子树|前驱_[LeetCode]剑指Offer36.二叉搜索树与双向链表

篇首语：本文由编程笔记#小编为大家整理，主要介绍了[LeetCode]剑指 Offer 36. 二叉搜索树与双向链表相关的知识，希望对你有一定的参考价值。

输入一棵二叉搜索树&＃xff0c;将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点&＃xff0c;只能调整树中节点指针的指向。

为了让您更好地理解问题&＃xff0c;以下面的二叉搜索树为例&＃xff1a;

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表&＃xff0c;第一个节点的前驱是最后一个节点&＃xff0c;最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地&＃xff0c;我们希望可以就地完成转换操作。当转化完成以后&＃xff0c;树中节点的左指针需要指向前驱&＃xff0c;树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

题解&＃xff1a;

将 二叉搜索树 转换成一个 “排序的循环双向链表” &＃xff0c;其中包含三个要素&＃xff1a;

1. 排序链表&＃xff1a; 节点应从小到大排序&＃xff0c;因此应使用 中序遍历 “从小到大” 访问树的节点。
2. 双向链表&＃xff1a; 在构建相邻节点的引用关系时&＃xff0c;设前驱节点 pre 和当前节点 cur &＃xff0c;应构建 pre.right &＃61; cur &＃xff0c;cur.left &＃61; pre 。
3. 循环链表&＃xff1a; 设链表头节点 head 和尾节点 tail &＃xff0c;则应构建 head.left &＃61; tail 和 tail.right &＃61; head 。

算法流程&＃xff1a;

treeToDoublyList(root)&＃xff1a;

1. 特例处理&＃xff1a; 若节点 root 为空&＃xff0c;则直接返回&＃xff1b;
2. 初始化&＃xff1a; 空节点 pre &＃xff1b;
3. 转化为双向链表&＃xff1a; 调用 dfs(root) &＃xff1b;
4. 构建循环链表&＃xff1a; 中序遍历完成后&＃xff0c;head 指向头节点&＃xff0c; pre 指向尾节点&＃xff0c;因此修改 head 和 pre 的双向节点引用即可&＃xff1b;
5. 返回值&＃xff1a; 返回链表的头节点 head 即可&＃xff1b;

dfs(cur)&＃xff1a;递归法中序遍历

1. 终止条件&＃xff1a; 当节点 cur 为空&＃xff0c;代表越过叶节点&＃xff0c;直接返回&＃xff1b;
2. 递归左子树&＃xff0c;即 dfs(cur.left) &＃xff1b;
3. 构建链表&＃xff1a;
   
   • 当 pre 为空时&＃xff1a; 代表正在访问链表头节点&＃xff0c;记为 head &＃xff1b;
   • 当 pre 不为空时&＃xff1a; 修改双向节点引用&＃xff0c;即 pre.right &＃61; cur &＃xff0c; cur.left &＃61; pre &＃xff1b;
   • 保存 cur &＃xff1a; 更新 pre &＃61; cur &＃xff0c;即节点 cur 是后继节点的 pre &＃xff1b;
4. 递归右子树&＃xff0c;即 dfs(cur.right) &＃xff1b;

class Solution
Node pre;
Node head;
/**
* 剑指 Offer 36. 二叉搜索树与双向链表
*/
public Node treeToDoublyList(Node root)
if (root &＃61;&＃61; null)
return null;

// 构建双向链表
dfs(root);
// 构建循环链表
head.left &＃61; pre;
pre.right &＃61; head;
return head;

void dfs(Node cur)
if (cur &＃61;&＃61; null)
return;

// 递归左子树
dfs(cur.left);
// pre.right &＃61; cur; cur.left &＃61; pre; pre &＃61; cur;
if (pre !&＃61; null)
pre.right &＃61; cur;
else
head &＃61; cur;

cur.left &＃61; pre;
pre &＃61; cur;
// 递归右子树
dfs(cur.right);




来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
链接&＃xff1a;https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof